// https://leetcode-cn.com/problems/target-sum/

// 法一：回溯
class Solution {
public:
    
    void getAns(vector<int>& nums, int start, int sum, int target, int& total) {
        // if (start == nums.size() && sum == target) {
        if (start == nums.size()) {
            if (sum == target) {
                total++; //或者把total作为类变量
            }
            return;
        }
        // 这边每个元素都要用上，所以不能用循环，不然没有用所有元素的情况也会被算上，因为当循环到后一个的时候实际上就是push_back再pop_back了
        // for (int i = start; i < nums.size(); ++i) {
        // getAns(nums, tmp, i + 1, sum + nums[i], target, total);
        // getAns(nums, tmp, i + 1, sum - nums[i], target, total);
        // }
       
        getAns(nums, start + 1, sum + nums[start], target, total);
        getAns(nums, start + 1, sum - nums[start], target, total);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0;
        int start = 0;
        int sum = 0;
        getAns(nums, start, sum, target, total);
        return total;
    }
};

// 法二：转换为0-1背包
// https://leetcode-cn.com/problems/target-sum/solution/mu-biao-he-by-leetcode-solution-o0cp/
// 问题转化成在数组中选取若干元素，使得这些元素之和等于neg，计算选取元素的方案数。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int n: nums) {
            sum += n;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 == 1) return 0;
        int neg = diff / 2;
        vector<int> rec(neg + 1, 0);
        rec[0] = 1; //注意！！
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = neg; j >= nums[i]; --j) {
                rec[j] += rec[j - nums[i]]; 
            }
        }
        return rec.back();
    }
};